Valid parentheses¶
Time: O(N); Space: O(N); easy
Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ’]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: str = “()”
Output: True
Example 2:
Input: str = “()”
Output: True
Example 3:
Input: str = “(]”
Output: False
Example 4:
Input: str = “([)]”
Output: False
Example 5:
Input: str = “{[]}”
Output: True
[1]:
class Solution1(object):
def isValid(self, s: str) -> bool:
"""
:type str: string
:rtype: bool
"""
stack, lookup = [], {"(": ")", "{": "}", "[": "]"}
for parenthese in s:
if parenthese in lookup:
stack.append(parenthese)
elif len(stack) == 0 or lookup[stack.pop()] != parenthese:
return False
return len(stack) == 0
[2]:
s = Solution1()
str = "()"
assert s.isValid(str) == True
str = "()[]{}"
assert s.isValid(str) == True
str = "(]"
assert s.isValid("()[{]}") == False
str = "([)]"
assert s.isValid("()[{]}") == False
str = "{[]}"
assert s.isValid(str) == True